# -*- coding: utf-8 -*-

'''
bubble.py
Created on Junho de 2013
@authors: 
    Ricardo Barros, ESTIG,  EI pós-laboral n.º 5137
    Sergio Santos, ESTIG,  EI pós-laboral n.º 5626
'''

"""
O algoritmo "Bubble Sort"

Tempo de execução:
    Complexidade pior caso O(n^2);
    Complexidade caso médio O(n^2);
    Complexidade melhor caso: O(n)

O bubble sort, ou ordenação por flutuação (literalmente "por bolha"), é um algoritmo 
de ordenação dos mais simples. A ideia é percorrer o vector diversas vezes, a cada 
passagem fazendo flutuar para o topo o maior elemento da sequência.

No melhor caso, o algoritmo executa  operações relevantes, onde n representa o número 
de elementos do vector. 
No pior caso, são feitas  operações. 

A complexidade desse algoritmo é de Ordem quadrática. Por isso, ele não é recomendado 
para programas que precisem de velocidade e operem com quantidade elevada de dados.

Como utilizar:
 - EXEMPLO: Ordenação do array A:
 
    A = [10, 11, 12, 3, 13, 13, 14, 15, 16, 17, 2, 4, 5, 7, 1, 2, 3, 6, 20, 21]
    print "antes A: ", A
    bubbleSort(A)
    print "depois A:", A

antes A:  [10, 11, 12, 13, 13, 14, 15, 16, 17, 2, 4, 5, 7, 1, 2, 3, 6, 20, 21]
depois A: [1, 2, 2, 3, 4, 5, 6, 7, 10, 11, 12, 13, 13, 14, 15, 16, 17, 20, 21]
>>>

"""


def bubbleSort(A):
    for i in xrange(0, len(A)):
        for j in xrange(len(A)-1, i, -1 ):
            if A[j] < A[j-1]:
                A[j], A[j-1] = A[j-1], A[j]


def main():
    A = [10, 11, 12, 3, 13, 13, 14, 15, 16, 17, 2, 4, 5, 7, 1, 2, 3, 6, 20, 21]
    print "antes A: ", A
    bubbleSort(A)
    print "depois A:", A


if __name__ == '__main__':
    main()